/********************************************
 *        Fonctions de recherche de         *
 *             clique maximale              *
 *                                          *
 *            clique_maximale.c             *
 *                                          *
 *     Grivolet Alenda Bourgeois Ciabaud    *
 ********************************************/
#include <stdlib.h>
#include <stdio.h>

#include "clique_maximale.h"
#include "structures.h"
#include "tests.h"

/* 
 * estComplet
 *
 * teste si le sous graphe de G induit par E est complet
 *
 * @param G	Graphe a tester
 * @param E	Ensemble de sommets qui forment le sous
 * 		graphe
 *
 * @return 	1 si le sous-graphe est complet
 * 		0 sinon
 *
 * Complexite: 	n+m
 * 		linéaire en la taille du graphe
 */
int estComplet( Graphe G, Ensemble E )
{
	int i, v, t=0;
	Maillon *tmp;

	/* Taille du sous-graphe */
	for(i=0;i<G.nbSommets;i++)
		if(E[i])
			t++;

	/* pour chaque sommet de G */
	for( i=0; i<G.nbSommets; i++)
	{
		/* S'il est dans le sous-graphe */
		if( E[i] )
		{
			/* On compte ses voisins */
			v = 0;
			FOREACH(tmp, G.Sommets[i])
			{
				if( E[tmp->elt] )
					v++;
			}

			/* si il n'est pas relie a tous les sommets
			 * il n est pas complet */
			if( v < t-1 ) return 0;
		}
	}

	return 1;	
}

/* 
 * genere_ensemble
 *
 * genere toutes les combinaisons de sommets de G 
 * dans E de k a nb
 *
 * @param G 	Le graphe a etudier
 * @param E 	L'ensemble a completer
 * @param k	Premier indice a generer
 * @param nb 	Taille de la generation
 *
 * Complexite: 	dans le pire des cas (pas de clique)
 * 		on genere toutes les partitions de E
 * 
 * 		On cree donc toute les partition d'un
 * 		ensemble de taille nb. Donc la complexite
 * 		est le nombre de 2^n
 * 		Donc complexite 0(2^n) (NP-Merci)
 */
Ensemble genere_ensemble(Graphe G, Ensemble E, int k, int nb)
{

	/* Si on a genere une combinaison */
	if(nb == 0)
	{
		/* On regarde si il est complet */
		if( estComplet(G, E) )
			return E;
		else
			return NULL;
	}
	else
	{
		
		/* 1er cas */
		E[k] = 1;
		/* On genere Les combinaisons */
		if( genere_ensemble(G, E, k+1, nb-1) != NULL )
			return E;
		/* 2e cas */
		E[k] = 0;
		/* On genere Les combinaisons */
		if( genere_ensemble(G, E, k+1, nb-1) != NULL )
			return E;
			
	}
	
	return NULL;
	
}

/* 
 * clique_maximale
 *
 * cherche la clique maximale de G
 *
 * @param G	Graphe a etudier
 *
 * @return 	Ensemble symbolisant la clique max
 *
 * Complexite: 	exponentielle d'apres la generation
 */
Ensemble clique_maximale( Graphe G ){

	Ensemble E;
	
	/* Creation dynamique de E */
	E = calloc(G.nbSommets, sizeof(int) );
	
	start_clock();

	/* Si on trouve un sous graphe triangule on s'arrete */
	if( genere_ensemble(G, E, 0, G.nbSommets) != NULL ){
		end_clock();
		return E;
	}

	end_clock();
		
	/* On a rien trouve */
	return NULL;

}

